#include "gtest/gtest.h"
#include "viml/compiler.h"
#include "viml/vm.h"
#include <chrono>

using namespace viml;

class MemoizationTest : public ::testing::Test {
protected:
    Compiler compiler;
    VM vm;
    
    void SetUp() override {
        // 为每个测试重置编译器和虚拟机
        compiler.reset();
        vm.reset();
        
        // 启用记忆化
        vm.set_memoization_enabled(true);
        
        // 为递归算法优化缓存配置
        vm.optimize_memoization_for_recursive_algorithms();
    }
    
    Value execute_source(const std::string& source) {
        auto bytecode = compiler.compile(source, "<test>");
        return vm.execute(bytecode);
    }
    
    struct PerformanceMetrics {
        double execution_time_ms;
        size_t function_calls;
        MemoizationCache::Statistics cache_stats;
    };
    
    PerformanceMetrics measure_performance(const std::string& source, const std::string& test_name = "test") {
        auto start_time = std::chrono::high_resolution_clock::now();
        
        // 重置统计信息
        vm.reset_statistics();
        vm.clear_memoization_cache();
        
        // 执行代码
        Value result = execute_source(source);
        
        auto end_time = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
        
        PerformanceMetrics metrics;
        metrics.execution_time_ms = duration.count() / 1000.0;
        metrics.function_calls = vm.get_statistics().function_calls;
        metrics.cache_stats = vm.get_memoization_statistics();
        
        return metrics;
    }
};

// MM-001: 基础记忆化功能测试
TEST_F(MemoizationTest, BasicMemoizationFunctionality) {
    std::string source = R"(
        function simple_add(a, b)
            return a + b
        endfunction
        
        " 手动添加到可记忆化函数列表
        let result1 = simple_add(3, 4)
        let result2 = simple_add(3, 4)  " 应该命中缓存
        let result3 = simple_add(5, 6)  " 不同参数，应该计算
        let result4 = simple_add(3, 4)  " 再次命中缓存
    )";
    
    // 添加函数到可记忆化列表
    vm.add_memoizable_function("simple_add");
    
    Value result = execute_source(source);
    
    // 验证结果正确性
    EXPECT_TRUE(vm.has_global("result1"));
    EXPECT_TRUE(vm.has_global("result2"));
    EXPECT_TRUE(vm.has_global("result3"));
    EXPECT_TRUE(vm.has_global("result4"));
    
    EXPECT_EQ(vm.get_global("result1").as_number(), 7.0);
    EXPECT_EQ(vm.get_global("result2").as_number(), 7.0);
    EXPECT_EQ(vm.get_global("result3").as_number(), 11.0);
    EXPECT_EQ(vm.get_global("result4").as_number(), 7.0);
    
    // 验证缓存统计
    auto cache_stats = vm.get_memoization_statistics();
    EXPECT_GT(cache_stats.hits, 0);  // 应该有缓存命中
    EXPECT_GT(cache_stats.hit_rate, 0.0);  // 命中率应该大于0
}

// MM-002: 斐波那契递归记忆化性能测试
TEST_F(MemoizationTest, FibonacciMemoizationPerformance) {
    std::string fibonacci_source = R"(
        function Fibonacci(n)
            if n <= 1
                return n
            endif
            
            return Fibonacci(n - 1) + Fibonacci(n - 2)
        endfunction
        
        let result = Fibonacci(15)
    )";
    
    // 测试无记忆化的性能
    vm.set_memoization_enabled(false);
    auto metrics_no_memo = measure_performance(fibonacci_source, "Fibonacci_NoMemo");
    
    // 测试有记忆化的性能
    vm.set_memoization_enabled(true);
    vm.add_memoizable_function("Fibonacci");
    auto metrics_with_memo = measure_performance(fibonacci_source, "Fibonacci_WithMemo");
    
    // 验证结果正确性
    EXPECT_TRUE(vm.has_global("result"));
    EXPECT_EQ(vm.get_global("result").as_number(), 610.0);  // Fibonacci(15) = 610
    
    // 验证性能提升
    EXPECT_LT(metrics_with_memo.execution_time_ms, metrics_no_memo.execution_time_ms);
    std::cout << "性能对比 Fibonacci(15):" << std::endl;
    std::cout << "  无记忆化: " << metrics_no_memo.execution_time_ms << "ms, " 
              << metrics_no_memo.function_calls << " 函数调用" << std::endl;
    std::cout << "  有记忆化: " << metrics_with_memo.execution_time_ms << "ms, " 
              << metrics_with_memo.function_calls << " 函数调用" << std::endl;
    std::cout << "  性能提升: " << (metrics_no_memo.execution_time_ms / metrics_with_memo.execution_time_ms) 
              << "倍" << std::endl;
    
    // 验证缓存统计
    EXPECT_GT(metrics_with_memo.cache_stats.hits, 0);
    std::cout << "  缓存统计: " << metrics_with_memo.cache_stats.hits << " 命中, " 
              << metrics_with_memo.cache_stats.misses << " 未命中, " 
              << "命中率 " << metrics_with_memo.cache_stats.hit_rate << "%" << std::endl;
}

// MM-003: 更大的斐波那契测试（验证显著性能提升）
TEST_F(MemoizationTest, FibonacciLargeScale) {
    std::string fibonacci_source = R"(
        function Fibonacci(n)
            if n <= 1
                return n
            endif
            
            return Fibonacci(n - 1) + Fibonacci(n - 2)
        endfunction
        
        let result = Fibonacci(20)
    )";
    
    // 只测试有记忆化的版本（无记忆化版本会太慢）
    vm.set_memoization_enabled(true);
    vm.add_memoizable_function("Fibonacci");
    auto metrics = measure_performance(fibonacci_source, "Fibonacci_20");
    
    // 验证结果正确性
    EXPECT_TRUE(vm.has_global("result"));
    EXPECT_EQ(vm.get_global("result").as_number(), 6765.0);  // Fibonacci(20) = 6765
    
    // 验证性能（应该在合理时间内完成）
    EXPECT_LT(metrics.execution_time_ms, 1000.0);  // 应该在1秒内完成
    
    // 验证缓存效果
    // 对于Fibonacci(20)，理论分析：
    // - 必须计算21个唯一值: Fib(0) 到 Fib(20)，每个首次计算时必然miss（21次miss）
    // - 重复访问的数字会命中缓存（约18次hit）
    // - 理论最优命中率 ≈ 18/(18+21) ≈ 46%，这是算法特性决定的
    EXPECT_GT(metrics.cache_stats.hits, 15);  // 应该有显著的命中次数（期望约18次）
    EXPECT_GT(metrics.cache_stats.hit_rate, 40.0);  // 命中率应该超过40%（理论约46%）
    EXPECT_LT(metrics.cache_stats.hit_rate, 50.0);  // 对于Fibonacci算法，命中率理论上不会超过50%
    
    // 验证缓存大小合理（应该缓存了0-20共21个值）
    EXPECT_LE(metrics.cache_stats.size, 21);  // 缓存的唯一值不应超过21个
    
    // 验证没有缓存淘汰（缓存容量50 > 需要的21）
    EXPECT_EQ(metrics.cache_stats.evictions, 0);  // 不应该有淘汰
    
    std::cout << "Fibonacci(20) 记忆化性能:" << std::endl;
    std::cout << "  执行时间: " << metrics.execution_time_ms << "ms" << std::endl;
    std::cout << "  函数调用: " << metrics.function_calls << " 次" << std::endl;
    std::cout << "  缓存命中: " << metrics.cache_stats.hits << " 次" << std::endl;
    std::cout << "  缓存未命中: " << metrics.cache_stats.misses << " 次" << std::endl;
    std::cout << "  命中率: " << metrics.cache_stats.hit_rate << "%" << std::endl;
    std::cout << "  缓存大小: " << metrics.cache_stats.size << " 个唯一值" << std::endl;
    std::cout << "  淘汰次数: " << metrics.cache_stats.evictions << std::endl;
}

// MM-004: 记忆化管理接口测试
TEST_F(MemoizationTest, MemoizationManagementInterface) {
    // 测试启用/禁用记忆化
    EXPECT_TRUE(vm.is_memoization_enabled());
    
    vm.set_memoization_enabled(false);
    EXPECT_FALSE(vm.is_memoization_enabled());
    
    vm.set_memoization_enabled(true);
    EXPECT_TRUE(vm.is_memoization_enabled());
    
    // 测试函数白名单管理
    vm.add_memoizable_function("test_function");
    vm.add_memoizable_function("another_function");
    
    // 清空缓存
    vm.clear_memoization_cache();
    auto stats = vm.get_memoization_statistics();
    EXPECT_EQ(stats.size, 0);
    EXPECT_EQ(stats.hits, 0);
    EXPECT_EQ(stats.misses, 0);
}

// MM-005: 参数类型兼容性测试
TEST_F(MemoizationTest, ParameterTypeCompatibility) {
    std::string source = R"(
        function type_test(num, bool_val, str_val)
            if bool_val
                return num + len(str_val)
            else
                return num
            endif
        endfunction
        
        let result1 = type_test(10, 1, "hello")   " 10 + 5 = 15
        let result2 = type_test(10, 1, "hello")   " 应该命中缓存
        let result3 = type_test(10, 0, "hello")   " 不同布尔值
        let result4 = type_test(20, 1, "world")   " 不同参数
    )";
    
    vm.add_memoizable_function("type_test");
    
    Value result = execute_source(source);
    
    // 验证结果正确性
    EXPECT_EQ(vm.get_global("result1").as_number(), 15.0);
    EXPECT_EQ(vm.get_global("result2").as_number(), 15.0);
    EXPECT_EQ(vm.get_global("result3").as_number(), 10.0);
    EXPECT_EQ(vm.get_global("result4").as_number(), 25.0);
    
    // 验证缓存统计
    auto cache_stats = vm.get_memoization_statistics();
    EXPECT_GT(cache_stats.hits, 0);  // 至少result2应该命中缓存
}

// MM-006: 缓存容量和LRU测试
TEST_F(MemoizationTest, CacheLRUBehavior) {
    std::string source = R"(
        function cache_test(x)
            return x * x
        endfunction
    )";
    
    vm.add_memoizable_function("cache_test");
    
    // 执行基础代码定义函数
    execute_source(source);
    
    // 生成大量不同的函数调用，超过缓存容量
    const int CACHE_SIZE = 50;  // 斐波那契优化后的缓存大小
    const int CALL_COUNT = CACHE_SIZE + 10;
    
    for (int i = 0; i < CALL_COUNT; ++i) {
        std::string call_source = "let result" + std::to_string(i) + " = cache_test(" + std::to_string(i) + ")";
        execute_source(call_source);
    }
    
    auto cache_stats = vm.get_memoization_statistics();
    
    // 验证缓存大小不超过限制
    EXPECT_LE(cache_stats.size, static_cast<size_t>(CACHE_SIZE));
    
    // 验证有淘汰发生
    EXPECT_GT(cache_stats.evictions, 0);
    
    std::cout << "缓存LRU测试结果:" << std::endl;
    std::cout << "  缓存大小: " << cache_stats.size << "/" << CACHE_SIZE << std::endl;
    std::cout << "  淘汰次数: " << cache_stats.evictions << std::endl;
    std::cout << "  总调用: " << CALL_COUNT << std::endl;
}

// MM-007: 性能基准对比测试
TEST_F(MemoizationTest, PerformanceBenchmark) {
    std::string factorial_source = R"(
        function factorial(n)
            if n <= 1
                return 1
            endif
            return n * factorial(n - 1)
        endfunction
        
        let result = factorial(10)
    )";
    
    // 无记忆化版本
    vm.set_memoization_enabled(false);
    auto no_memo_metrics = measure_performance(factorial_source, "Factorial_NoMemo");
    
    // 有记忆化版本
    vm.set_memoization_enabled(true);
    vm.add_memoizable_function("factorial");
    auto memo_metrics = measure_performance(factorial_source, "Factorial_WithMemo");
    
    // 验证结果正确性
    EXPECT_EQ(vm.get_global("result").as_number(), 3628800.0);  // 10! = 3628800
    
    // 输出性能对比
    std::cout << "阶乘函数性能基准测试:" << std::endl;
    std::cout << "  无记忆化: " << no_memo_metrics.execution_time_ms << "ms" << std::endl;
    std::cout << "  有记忆化: " << memo_metrics.execution_time_ms << "ms" << std::endl;
    
    if (memo_metrics.execution_time_ms > 0) {
        double speedup = no_memo_metrics.execution_time_ms / memo_metrics.execution_time_ms;
        std::cout << "  性能提升: " << speedup << "倍" << std::endl;
    }
    
    std::cout << "  缓存命中率: " << memo_metrics.cache_stats.hit_rate << "%" << std::endl;
}